package main.sort;

public class InsertionSort extends BaseSort {
    public InsertionSort(int[] array) {
        super(array);
        this.name = "插入排序";
    }

    /**
     * 假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的
     * <br>
     * [7, 8, 6, 5, 4, 3, 2, 1]<br>
     * [6, 7, 8, 5, 4, 3, 2, 1]<br>
     * [5, 6, 7, 8, 4, 3, 2, 1]<br>
     * [4, 5, 6, 7, 8, 3, 2, 1]<br>
     * [3, 4, 5, 6, 7, 8, 2, 1]<br>
     * [2, 3, 4, 5, 6, 7, 8, 1]<br>
     * [1, 2, 3, 4, 5, 6, 7, 8]
     */
    @Override
    public void sort() {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                if (array[j - 1] > array[j]) {
                    swap(array, j - 1, j);
                } else {
                    break;
                }
            }
            print();
        }
    }
}
